home *** CD-ROM | disk | FTP | other *** search
/ SPACE 1 / SPACE - Library 1 - Volume 1.iso / program / 441 / dlibs12 / qsort.c < prev    next >
C/C++ Source or Header  |  1990-11-23  |  3KB  |  157 lines
  1. #include <stddef.h>
  2.  
  3. extern    char    *memcpy();
  4.  
  5. char    *_qbuf = NULL;        /* pointer to storage for qsort() */
  6.  
  7. #define    PIVOT            ((i+j)>>1)
  8. #define moveitem(dst,src,size)    if(dst != src) memcpy(dst, src, size)
  9.  
  10. static _wqsort(base, lo, hi, cmp)
  11.     register int *base;
  12.     register int lo;
  13.     register int hi;
  14.     register int (*cmp)();
  15.     {
  16.     int k;
  17.     register int i, j, t;
  18.     register int *p = &k;
  19.  
  20.     while(hi > lo)
  21.         {
  22.         i = lo;
  23.         j = hi;
  24.         t = PIVOT;
  25.         *p = base[t];
  26.         base[t] = base[i];
  27.         base[i] = *p;
  28.         while(i < j)
  29.             {
  30.             while(((*cmp)((base+j), p)) > 0)
  31.                 --j;
  32.             base[i] = base[j];
  33.             while((i < j) && (((*cmp)((base+i), p)) <= 0))
  34.                 ++i;
  35.             base[j] = base[i];
  36.             }
  37.         base[i] = *p;
  38.         if((i - lo) < (hi - i))
  39.             {
  40.             _wqsort(base, lo, (i - 1), cmp);
  41.             lo = i + 1;
  42.             }
  43.         else
  44.             {
  45.             _wqsort(base, (i + 1), hi, cmp);
  46.             hi = i - 1;
  47.             }
  48.         }
  49.     }
  50.  
  51. static _lqsort(base, lo, hi, cmp)
  52.     register long *base;
  53.     register int lo;
  54.     register int hi;
  55.     register int (*cmp)();
  56.     {
  57.     long k;
  58.     register int i, j, t;
  59.     register long *p = &k;
  60.  
  61.     while(hi > lo)
  62.         {
  63.         i = lo;
  64.         j = hi;
  65.         t = PIVOT;
  66.         *p = base[t];
  67.         base[t] = base[i];
  68.         base[i] = *p;
  69.         while(i < j)
  70.             {
  71.             while(((*cmp)((base+j), p)) > 0)
  72.                 --j;
  73.             base[i] = base[j];
  74.             while((i < j) && (((*cmp)((base+i), p)) <= 0))
  75.                 ++i;
  76.             base[j] = base[i];
  77.             }
  78.         base[i] = *p;
  79.         if((i - lo) < (hi - i))
  80.             {
  81.             _lqsort(base, lo, (i - 1), cmp);
  82.             lo = i + 1;
  83.             }
  84.         else
  85.             {
  86.             _lqsort(base, (i + 1), hi, cmp);
  87.             hi = i - 1;
  88.             }
  89.         }
  90.     }
  91.  
  92. static _nqsort(base, lo, hi, size, cmp)
  93.     register char *base;
  94.     register int lo;
  95.     register int hi;
  96.     register int size;
  97.     register int (*cmp)();
  98.     {
  99.     register int i, j;
  100.     register char *p = _qbuf;
  101.  
  102.     while(hi > lo)
  103.         {
  104.         i = lo;
  105.         j = hi;
  106.         p = (base+size*PIVOT);
  107.         moveitem(_qbuf, p, size);
  108.         moveitem(p, (base+size*i), size);
  109.         moveitem((base+size*i), _qbuf, size);
  110.         p = _qbuf;
  111.         while(i < j)
  112.             {
  113.             while(((*cmp)((base+size*j), p)) > 0)
  114.                 --j;
  115.             moveitem((base+size*i), (base+size*j), size);
  116.             while((i < j) && (((*cmp)((base+size*i), p)) <= 0))
  117.                 ++i;
  118.             moveitem((base+size*j), (base+size*i), size);
  119.             }
  120.         moveitem((base+size*i), p, size);
  121.         if((i - lo) < (hi - i))
  122.             {
  123.             _nqsort(base, lo, (i - 1), size, cmp);
  124.             lo = i + 1;
  125.             }
  126.         else
  127.             {
  128.             _nqsort(base, (i + 1), hi, size, cmp);
  129.             hi = i - 1;
  130.             }
  131.         }
  132.     }
  133.  
  134. qsort(base, num, size, cmp)
  135.     char *base;
  136.     int num;
  137.     int size;
  138.     int (*cmp)();
  139.     {
  140.     char _qtemp[128];
  141.  
  142.     if(_qbuf == NULL)
  143.         {
  144.         if(size > sizeof(_qtemp))    /* records too large! */
  145.             return;
  146.         _qbuf = _qtemp;
  147.         }
  148.     if(size == 2)
  149.         _wqsort(base, 0, num-1, cmp);
  150.     else if(size == 4)
  151.         _lqsort(base, 0, num-1, cmp);
  152.     else
  153.         _nqsort(base, 0, num-1, size, cmp);
  154.     if(_qbuf == _qtemp)
  155.         _qbuf = NULL;
  156.     }
  157.